/**
 * @Author: zxc
 * @Date: 2020-11-02 12:21:55
 * @func:寻找两个正序数组的中位数
 */

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
// var findMedianSortedArrays = function(nums1, nums2) {
//   const arr = [...nums1,...nums2].sort((a,b) => a-b)
//   const len = arr.length
//   if(len > 0 && len % 2 === 0){
//       return (arr[(len / 2) - 1] + arr[len / 2]) / 2
//   } else {
//       return arr[ ( len - 1 ) / 2]
//   }
// };

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
var findMedianSortedArrays = function (nums1, nums2) {
  const len1 = nums1.length,
    len2 = nums2.length
  if (len1 > len2) {
    return findMedianSortedArrays(nums2, nums1)
  }
  ƒ
  const len = len1 + len2
  let start = 0,
    end = len1,
    firstLen,
    nextLen
  while (start <= end) {
    firstLen = (start + end) >> 1 // 等同于parseInt((start +  end) / 2)
    nextLen = ((len + 1) >> 1) - firstLen
    const firstLeft = firstLen === 0 ? -Infinity : nums1[firstLen - 1],
      firstRight = firstLen === len1 ? Infinity : nums1[firstLen],
      nextLeft = nextLen === 0 ? -Infinity : nums2[nextLen - 1],
      nextRight = nextLen === len2 ? Infinity : nums2[nextLen]
    if (firstLeft > nextRight) {
      end = firstLen - 1
    } else if (nextLeft > firstRight) {
      start = firstLen + 1
    } else {
      return len % 2 === 0
        ? (Math.max(firstLeft, nextLeft) + Math.min(firstRight, nextRight)) / 2
        : Math.max(firstLeft, nextLeft)
    }
  }
}
